The increasing demand on the world's transportation capacity has led to a concerted effort by government and industry to develop an Intelligent Transportation System (ITS) for the future. Many such systems require Automatic Vehicle Location (AVL) to continuously pinpoint a vehicle's location on the roadways (or rail lines, etc.). An inexpensive, reliable, and accurate system for AVL is the key to applications such as personal navigation, centralized traffic monitoring, and public transportation control and dispatching.
Current proposals for AVL systems are based primarily on either the U.S. government's satellite-based Global Positioning System (GPS) or on transmitting beacons placed throughout the city (e.g. the Bosch/Blaupunkt and Siemens ALI-SCOUT system).
A common first step to automatic vehicle location (and other navigation problems) is dead-reckoning. Dead-reckoning estimates position by starting at some known initial location which is blindly updated according to the distance travelled, as measured by the odometer and the steering angle measured by a directional sensor. An odometer is a cheap and accurate sensor available in virtually any vehicle. Gyroscopic devices to measure turning angles (and hence help to decide which branch in a road is followed) are slightly more problematic, but can be implemented. The key obstacle to a system based entirely on dead-reckoning is the slow but inevitable accumulation of errors that the system cannot correct.
The use of omnidirectional vision navigation systems for providing video information useful in robot navigation, or for the location of mobile systems, is known in the art. For example, Zhongfei Zhang, Richard Weiss, and Edward M. Riseman, presented a paper on Apr. 3, 1991, entitled "Segment-Based Matching for Visual Navigation", Computer Information Science Department, University of Massachusetts, Amherst, Mass., "COINS PR91-35". The paper describes the use of a reflecting globe or spherical mirror, mounted on top of a mobile robot above a camera. The camera converts the picture received to a 360.degree. video image of the surrounding environment. The video image from the camera is processed for obtaining a fixed set of target locations for permitting a robot to navigate between desired locations by carrying out a sequence of homing tasks relative to the target locations. The 360.degree. view taken at a given time is condensed into a 1-dimensional location signature. Correlation techniques are used for providing matching between location signatures in navigating the robot. The location signature is represented by three types of segments identified as increasing, decreasing, and constant, respectively. In the system, a "horizon circle" is superimposed upon the 360.degree. image for taking a sample of the image every degree, that is taking 360 samples. The "horizon circle", together with the X and Y axes, is characterized as forming a circular band composed of 360 ticks. The circle is designated as being the actual horizon circle, with each tick being a sample thereof, as a function of the azimuth orientation. The resultant sequences of linear segments obtained are not all used for matching, whereby selective ones are obtained for providing "characteristic features" for matching between images, and navigating a robot to move from one image location to a next, in a successive manner. Each 360.degree. video image is processed using a spherical coordinate system centered upon the origin of the image plane. The "characteristic features" chosen for matching are those which appear to be most distinctive and reliable for such use, for example parts of the processed waveform having a large slope for feature transition.
Another paper by Sung Jun Oh and Ernest L. Hall, entitled "A Study of the Characteristics of a Omnidirectional Vision Sensor", was published in SPIE, Volume 804 of Advances and Image Processing in 1987, on pages 259 through 267. The detector of the system includes a fish eye lens mounted over a video camera, for projecting a 360.degree. image of its surroundings. The video camera consists of a CCD or charge coupled device camera for providing a video signal representative of the 360.degree. image to an image processing system.
Another known system for providing route recognition in robot navigation includes the use of a rotating slit in combination with a video camera for providing a video image band representative of a panoramic view of the environment a robot is to navigate. As the rotating slit camera apparatus is moved linearly the panoramic view changes. Successive 2D panoramic image strips are connected together for providing a continuous panoramic view relative to a robot moving through the chosen environment. The images are processed through use of circular dynamic programming to obtain vertical line segments from the images for use in matching techniques for guiding the robot as a robot's movement. The robot's signal processor compares its present panoramic view with recorded panoramic views in order to determine the robot's heading, and correct the same if it is off course. See J. Y. Zheng and S. Tsuji, "Panoramic Representation for Route Recognition by a Mobile Robot", International Journal of Computer Vision, Volume 9:1, pages 55-76 (1992), Kluwer Academic Publishers, The Netherlands. All of the above work relies on geometric modelling.
Prior vehicle location systems include some based upon the satellite Global Positioning System (GPS), which tend to function well in rural environments, but also tend to fail when applied for use in dense urban environments. Prior vehicle location systems tend to be relatively complex, expensive, and at times unreliable.
Also, the above-described prior omnidirectional vision navigation systems partly based upon taking panoramic views of surroundings associated with a route that a robot may travel, encounter further problems when operated outdoors because of environmental changes. For example, such changes may cause images taken at the same location but at different times during a day to differ dramatically, on a pixel-by-pixel basis. Illumination conditions vary throughout the day and night depending upon cloud cover, pollution, other weather conditions, seasons of the year, and so forth. Also, illumination often is not uniform across a given image. The sun may create glare in an image. Trees, buildings, and clouds may create shadows during the daytime, or even at night with artificial illumination. Also, portions of an image may be either under-illuminated or over-illuminated. Trees and buildings may be altered over the course of time, or over various seasons where the deciduous trees may lose their leaves, or sprout new leaves. Also, trees and shrubbery may be pruned, cut down, or simply fall down, at unpredictable times. Likewise, buildings or other structures may be erected or torn down from time to time. Night time imaging also presents major problems due to changing traffic lights, street lights, lights for buildings, and so forth, creating features that may or may not be usable for landmark recognition. Typically, such features due to light sources are not reliable in that traffic lights change color periodically, street lamps may burn out, and new lighting systems may be installed in different areas. Accordingly, vision-based systems must be able to operate reliably despite all of the aforesaid problems.
The capabilities of the prior omnidirectional vision navigation systems are also very limited. These systems operate on a predefined route. The route cannot have decision points, i.e., intersections. If the robot or the vehicle happens to go astray from the pre-defined route, these systems stop operating, even when the robot just goes astray for a short period of time and comes back on route again. These system do not have capabilities to recover from large errors. In fact, they probably don't know when errors occur.